zk-SNARKs | logic gates → R1CS → QAP
Computation
Algebraic Circuit
R1CS
QAP(quadratic arithmetic program)
Linear PCP
Linear Interactive Proof
zkSNARK
functionをQAPにinputできる形に変形した後outputとしてwitnessが生成し、それをzkpにしていく。
$ x^3 + x + 5 == 35の解(x=3)を知っていることをzkpする。
Flattening (Algebraic Circuit)
任意の複雑な表現をされたオリジナルのコードをx = yとx = y (op) zの２つの形で連続的な表現をしていく。opは+, -, *, /で、yとzは変数でも数字でもなり得る。
code: s1.js
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5
Gates to R1CS
R1CS(rank-1 constraint system)は、s . a * s . b - s . c = 0を満たす(a ,b, c)の3つのベクトルの配列。sはsolution vector。
https://gyazo.com/aecf78b2e6fc0d37b573e0c067b829ed
logic gatesを(a, b, c)に変換していく。
それぞれのベクトルの長さは、最初のindexに1を表すダミー変数~oneを置き、それに加えてシステムにおける変数の数の合計。
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
それぞれのgate（プロセス）におけるinputとoutputの辻褄が合うような(a ,b ,c)を与えていく。
sym_1 = x * xは、
code:1
y = sym_1 * xは、
code:2
sym_2 = y + xは、
code:3
（２つのinputの合計がoutputを一致するか確認するだけなので、bは~oneで1にする。）
~out = sym_2 + 5
code:4
結果的にR1CSは、長さが6（変数数+1)の3つのベクトル(A,B,C)の4つの集合(gate数)から成る。
code:s2.js
A
B
C
R1CS to QAP
R1CSからQAPの変換も、GatesからR1CSへの変換と同じように行うがドット積の代わりに多項式を利用する。つまり、ラグランジュの補間公式を利用することで長さ6の3つのベクトルの4つのグループのR1CSを3つの「6つの3次多項式のグループ」に変換する。ラグランジュの補間公式により、k個の点を通るk-1次多項式を一意に定めることができるので、 (1, 3), (2, 2), (3, 4)を通る二次曲線を考えるときまずは、(1, 3), (2, 0), (3, 0)を通る二次曲線を作ることを考える。
$ y = (x-2)(x-3)
https://gyazo.com/1fa4ad649dc53049dc19d346b7c6765a
(1, 3)を通るように、変換すると、
$ \frac{(x - 2)(x - 3) \times 3}{(1 - 2)(1 - 3)} = 1.5x^2 -7.5x + 9
https://gyazo.com/b4ac1eef48e0d5f41a14871f4d67137b
x=2, 3に関しても同様の操作を行い、それぞれの多項式を算出した上でそれら3つを足し合わせると以下の多項式を得る。（これがラグランジュの補間公式）
$ y= 1.5x^2 - 5.5x + 7
https://gyazo.com/71fb0e03788fb59daf6851b8019b2792
(1, 3), (2, 2), (3, 4)を通っている。
一般的に、
https://gyazo.com/627cbd634950658db0112ac6121b1b40https://gyazo.com/387faf170192604eb717e9623f9d4554
このアルゴリズムは、O(n**3)の計算量が必要になるが高速フーリエ変換などを用いることで計算量は大幅に減らすことが可能で、実践でzk-SNARKsを用いる関数は数千のgatesになるのでこのような最適化は超重要。
このラグランジュの補間公式をR1CSに適用し、QAPに変換していく。
例えば、R1CSのaベクトルの最初のindexの値(0, 0, 0, 5)から(1,0), (2, 0), (3, 0), (4, 5)の4点を通る3次多項式を復元する。
code:s3
A polynomials
B polynomials
C polynomials
それぞれの係数が昇順に並んでいるので、例えば最初の多項式は以下のようになる。
$ 0.833x^3 - 5x^2 + 9.166x -5
ここまでの、QAPのパラメーター生成は検証のためにzk-SNARKsを使おうとする関数ごとに1回ひつようになり、一度生成したら同じ関数に関しては使い回すことができる。
このような多項式への変換をすることにより、gatesに対応するそれぞれのR1CSではなく、多項式のドット積をチェックすることで全てのgatesを同時にチェックすることができる。R1CSだとgates数の4回ドット積をチェックする必要があった。さらに、複雑な関数になるとR1CSのままだと、数千ものgatesをチェックしなければならなくなってしまう。
https://gyazo.com/c2213e44e3e874269d52f15abe4f6d29
実際に計算すると、
code:5
例えば、$ 1 * (-5) + 3 * 8 + 35 * 0 + 9 * (-5) + 27 * 4 + 30 * (-1) = 43.0
$ t = A . s * B . s - C . sは、
$ t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
t自体はゼロにはならず、gateに対応するx=1,2,3,4を評価するのではなく、最小多項式Zで除算し余りがないことをチェックする。
最小多項式$ Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)は、
$ Z = [24, -50, 35, -10, 1]
（係数昇順）
よって、
$ h = t / Z = [-3.666, 17.055, -3.444]
余りがない。つまり、x=1,2,3,4が解であるということ。
もし、間違ったsだとt多項式のx=1,2,3,4の結果が0にならない。
これはつまり、P=AB - CがZで因数分解できる時に、P := HZであるということ。
Quadratic Arithmetic Programs: from Zero to Hero :